/**
 * 最长回文子串
 *
 * 描述
 * 对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
 *
 * 数据范围：
 * 1≤n≤1000
 *
 * 要求：
 * 空间复杂度 O(1)，
 * 时间复杂度 O(n^2)
 * 进阶:
 * 空间复杂度 O(n)，
 * 时间复杂度 O(n)
 */

/**
 * 中心扩展法, 选取一个中心字符, 向两边扩展 (这里注意细节, 可能是从一个字符开始扩展,
 * 也有可能是从两个字符开始扩展, 要分类讨论) 此方法时间复杂度最小
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(1)
 */

public class Main {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param  s string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String s) {
        int n = s.length();
        char[] ss = s.toCharArray();

        // len记录最长回文串的长度
        int len = 0;

        // 选取一个中心字符
        for (int i = 0; i < n; i++) {

            // 从一个字符开始
            int left = i, right = i;

            // 给越界情况
            while (left >= 0 && right < n) {

                // 如果两边字符不相等, 直接退出循环
                // 否则继续向两边扩展 (left--, right++)
                if (ss[left] != ss[right]) {
                    break;
                } else {
                    left--;
                    right++;
                }
            }

            // 记录更新情况
            // 注意: 因为这种方法在判断上有一个延迟, 所以 left和 right都会比平常有一各单位的偏移量
            // 我们需要主义好下标的映射问题
            if (right - left - 1 > len) {
                len = right - left - 1;
            }

            // 转到以两个字符为中心
            left = i;
            right = i + 1;

            while (left >= 0 && right < n) {
                if (ss[left] != ss[right]) {
                    break;
                } else {
                    left--;
                    right++;
                }
            }
            if (right - left - 1 > len) {
                len = right - left - 1;
            }
        }
        return len;
    }
}